package arrAndstr;

import java.util.*;

/*
    210. 课程表 II
 */
public class T210 {
    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        int index = 0;

        int[] nodePreNode = new int[numCourses];    // 每个节点的后缀节点数
        Arrays.fill(nodePreNode, 0);

        Map<Integer, List<Integer>>  map = new HashMap<>(); // 每个节点对应的后缀节点们

        for (int[] prerequisite : prerequisites) {
            int pre = prerequisite[1];
            int post = prerequisite[0];

            List<Integer> list = map.get(pre) == null ? new ArrayList<>() : map.get(pre);
            list.add(post);
            map.put(pre, list);

            nodePreNode[post]++;
        }

        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < nodePreNode.length; i++) {
            if (nodePreNode[i] == 0)    queue.add(i);
        }

        if (queue.isEmpty())    return new int[0];
        int[] result = new int[numCourses];
        while (!queue.isEmpty()) {
            Integer num = queue.poll();
            result[index++] = num;

            List<Integer> list = map.get(num);
            if (list != null) {
                for (Integer i : list) {
                    nodePreNode[i]--;
                    if (nodePreNode[i]==0)  queue.add(i);
                }
            }
        }

        return queue.isEmpty()&&index==numCourses+1 ? result : new int[0];
    }

    public static void main(String[] args) {
        int numCourses = 2;
        int[][] prerequisites = new int[][] {
                {1,0},
//                {0,1},
//            {4,1},
//            {4,2},
//            {5,3},
//            {5,4}
        };

        for (int i : findOrder(numCourses, prerequisites)) {
            System.out.println(i);
        }
    }
}
